package algocasts;

import java.util.Arrays;

public class P132_FirstUniqChar {
    // Time: O(n)  Space: O(m)
    public int firstUniqChar_TwoPass(String s) {
        if (s == null || s.length() == 0) return -1;
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++)
            ++count[s.charAt(i) - 'a'];
        for (int i = 0; i < s.length(); i++)
            if (count[s.charAt(i) - 'a'] == 1)
                return i;
        return -1;
    }

    // Time: O(n)  Space: O(m)
    public int firstUniqChar_OnePass(String s) {
        if (s == null || s.length() == 0) return -1;
        int[] count = new int[26];
        int[] pos = new int[26];
        Arrays.fill(pos, -1);
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            ++count[idx];
            if (pos[idx] == -1) pos[idx] = i;
        }
        int firstPos = Integer.MAX_VALUE;
        for (int i = 0; i < 26; i++)
            if (count[i] == 1)
                firstPos = Math.min(firstPos, pos[i]);
        return firstPos == Integer.MAX_VALUE ? -1 : firstPos;
    }

}
